#include "DGraph.h"
#include "DGraphUtil.h"
#include "TestReachability.h"
#include <sys/time.h>
#include "headers.h"

using namespace std;

static void usage() {
	cout << "\nUsage:\n"
		"	g-hop [-h] [-d]  [-n num_query] [-p opt-type] [-f result-file] graph-file\n"
		"Description:\n"
		"	-h	Print the help message.\n"
		"	-d	Debug mode.\n"
		"	-c	Utility vector is cached.\n"
		"	-n	Set the total number of random queries. The default value is 100,000.\n"
		"	-f	Set the result filename ('../results.txt' is default file).\n"
	 	"	-r	Set the ratio of bipartites to be generated.\n"
		"	-t	Algorithm type(Three_Hop is default algorithm).\n"
		"		1:	Three_Hop\n"
		"	filename	The graph file.\n" << endl;
}

//int main(int argc, char* argv[]) {
//	const char *filename = "dataset_sigmod08/synthetic_data/rand2_20k.gra";
//	ifstream infile(filename);
//	DGraph graph(linfile);
//	cout<<"density:"<<1.0*graph.number_of_edges()/graph.number_of_vertices();
//
//}

int main(int argc, char* argv[]) {

	//const char *filename = "dataset_sigmod08\\real_data\\amaze.gra";
	//const char *filename = "my_test_data\\spanning_tree_test.gra";
	//const char *filename = "my_test_data\\divide_NTE_test.gra";
	//const char *filename = "my_test_data\\uncovered_transitive_closure_test.gra";
	//const char *filename = "my_test_data\\label_grid_hop_test_2.gra";


	//	const char *filename = argv[1];


	//	const char *filename ="label_grid_hop_test_2.gra";// "2k_2_12/rand2k_2.gra";
	//	const char *filename ="2k_2_12/rand2k_8.gra";
	//	const char *filename ="real/pubmed_sub_9000-1.gra";
	//	const char *filename ="real/go_sub_6793.gra";
	//	const char *filename ="real/go_sub_6793.gra";


	int i = 1;
	int query_num = 100000;
	int opt_type = 0;
	bool debug = false;

	char* filename = NULL;
	char* resfilename = "res_default_gg";

	while (i < argc) {
		if (strcmp("-h", argv[i]) == 0) {
			usage();
			return 1;
		}

		if (strcmp("-n", argv[i]) == 0) {
			i++;
			query_num = atoi(argv[i++]);
		} else if (strcmp("-d", argv[i]) == 0) {
			debug = true;
			i++;
		} else if (strcmp("-p", argv[i]) == 0) {
			i++;
			opt_type = atoi(argv[i++]);
		} else if (strcmp("-f", argv[i]) == 0) {
			i++;
			resfilename = argv[i++];
		} else {
			//			i++;
			filename = argv[i++];
		}
	}

	//	query_num=20;

	ofstream out(resfilename, ios::app);

	struct timeval after_time, before_time;
	float labeling_time, query_time1, query_time2;
	//	int total_pairs, covered_pairs;

	int labelsize = 0;
	//ifstream infile("my_test_data/uncovered_transitive_closure_test.gra");
	//ifstream infile("real_data/amaze.gra");
	//	ifstream infile("real/pubmed_sub_9000-1.gra");
	//	ifstream infile("real/arXiv_sub_6000-1.gra");
	//	const char *filename = argv[1];
	//	ifstream infile(filename);
	//			ifstream infile("2k_2_12/rand2k_4.gra");
	//	ifstream infile("real_data/nasa.gra");
	//	ifstream infile("real/yago_sub_6642.gra");
	//		ifstream infile("real_data/xmark.gra");
	//	ifstream infile("rand2_10k.gra");
	//	ifstream infile("my_test_data/divide_NTE_test.gra");
	//	ifstream infile("10k_2_25/rand10k_5.gra");
	ifstream infile("2k_2_12/rand2k_8.gra");
	//	ifstream infile("synthetic_data/rand2_100k.gra");
	//	const char *filename = "my_test_data\\divide_NTE_test.gra";
	if (infile) {
		cout << "opt type:" << opt_type << endl;
		cout << "read the graph file:" << filename << endl;
		DGraph graph(infile);
		cout << "#vertex size:" << graph.number_of_vertices()
				<< "\t#edges size:" << graph.number_of_edges() << endl;
		// merge strongly connected component
		int* sccmap = new int[graph.number_of_vertices()]; // store pair of orignal vertex and corresponding vertex in merged graph
		vector<int> reverse_topo_sort;
		cout << "merging strongly connected components..." << endl;
		DGraphUtil::merge_SCC(graph, sccmap, reverse_topo_sort);
		cout << "merging strongly connected components finished." << endl;
		cout << "#DAG vertex size:" << graph.number_of_vertices()
				<< "\t#DAG edges size:" << graph.number_of_edges() << endl;

		if (opt_type != 0) {
			gettimeofday(&before_time, NULL);
			DGraphUtil::opt_topological_sort(graph, reverse_topo_sort, opt_type);

			//	graph.write_graph(cout);
		} else {
			gettimeofday(&before_time, NULL);
		}
		TestReachability tester(graph);
		tester.test();
		//		tester.print_label(cout);
		gettimeofday(&after_time, NULL);
		labeling_time = (after_time.tv_sec - before_time.tv_sec) * 1000.0
				+ (after_time.tv_usec - before_time.tv_usec) * 1.0 / 1000.0;

		//		cout << "compute the uncovered ratio..." << endl;
		//		tester.uncovered_transitive_closure_evaluate(total_pairs, covered_pairs);

		//generate queries
		srand48(time(NULL));
		cout << "generating queries..." << endl;
		vector<int> src;
		vector<int> trg;
		vector<int>::iterator sit, tit;
		int s, t;
		int left = 0;
		int gsize = graph.number_of_vertices();

		//	int query_num = atoi(argv[4]);
		int failed = 0;
		bool r = false;

		while (left < query_num) {
			s = lrand48() % gsize;
			t = lrand48() % gsize;
			if (s == t)
				continue;
			src.push_back(s);
			trg.push_back(t);
			++left;
		}

		cout << "evaluate queries.." << endl;
		tester.sortByDFLN();
		tester.caculateTransitiveClosure();

		gettimeofday(&before_time, NULL);
		for (sit = src.begin(), tit = trg.begin(); sit != src.end(); ++sit, ++tit) {
			s = sccmap[*sit];
			t = sccmap[*tit];
			tester.reach(s, t);
		}
		gettimeofday(&after_time, NULL);
		query_time1 = (after_time.tv_sec - before_time.tv_sec) * 1000.0
				+ (after_time.tv_usec - before_time.tv_usec) * 1.0 / 1000.0;

		gettimeofday(&before_time, NULL);
		for (sit = src.begin(), tit = trg.begin(); sit != src.end(); ++sit, ++tit) {
			s = sccmap[*sit];
			t = sccmap[*tit];
			tester.reach_bak2(s, t);
		}
		gettimeofday(&after_time, NULL);
		query_time2 = (after_time.tv_sec - before_time.tv_sec) * 1000.0
				+ (after_time.tv_usec - before_time.tv_usec) * 1.0 / 1000.0;

		labelsize = tester.index_size();
		cout << "#g-label size=" << labelsize << "\t#total index size="
				<< labelsize + 2 * gsize << "\t #labeling time(ms)="
				<< labeling_time << "\t #query_time1(total, avarage)="
				<< query_time1 << "\t" << query_time1 / query_num<< "\t #query_time2(total, avarage)="
				<< query_time2 << "\t" << query_time2 / query_num
				<< "\t #forest=" << tester.getGraph()._tree.get_roots().size()
				<< endl;
		out << filename << "\t" << graph.number_of_vertices() << "\t"
				<< graph.number_of_edges() << "\t" << 1.0
				* graph.number_of_edges() / graph.number_of_vertices() << "\t"
				<< labelsize << "\t" << labelsize + 2 * gsize << "\t"
				<< labeling_time << "\t" << query_time1 << "\t" << query_time1
				/ query_num << "\t"  << query_time2 << "\t" << query_time2
				/ query_num<<endl
				<< tester.getGraph()._tree.get_roots().size()<< endl;
		cout << "end" << endl;
		//		cout<<tester.equalEndpoints<<"\t"<<tester.totalCheckHops<<endl;
		out.close();


	}

}
